package com.celan.year2023.month01.day02;

import java.util.*;

public class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        PriorityQueue<Integer> buyQue = new PriorityQueue<>((i1, i2) -> orders[i2][0] - orders[i1][0]);
        PriorityQueue<Integer> sellQue = new PriorityQueue<>((i1, i2) -> orders[i1][0] - orders[i2][0]);
        for (int i = 0; i < orders.length; i++) {
            int[] o = orders[i];
            int type = o[2], price = o[0];
            if (type == 0) { // o是采购订单buy
                while (!sellQue.isEmpty() && o[1] > 0) {
                    int[] q = orders[sellQue.peek()];
                    if (q[0] > price) break;
                    int min = Math.min(o[1], q[1]);
                    o[1] -= min;
                    q[1] -= min;
                    if (q[1] == 0) sellQue.poll();
                }
                if (o[1] > 0) buyQue.offer(i);
            } else { // o是销售订单 sell
                while (!buyQue.isEmpty() && o[1] > 0) {
                    int[] q = orders[buyQue.peek()];
                    if (q[0] < price) break;
                    int min = Math.min(o[1], q[1]);
                    o[1] -= min;
                    q[1] -= min;
                    if (q[1] == 0) buyQue.poll();
                    ;
                }
                if (o[1] > 0) sellQue.offer(i);
            }
        }

        int ret = 0;
        for (int[] o : orders) ret = (ret + o[1]) % (1000000007);
        return ret;
    }


    HashMap<Character, List<Integer>> dic = new HashMap<>();
    int[][] memo;
    String ring;
    String key;
    int n;
    int m;

    public int findRotateSteps(String ring, String key) {
        this.ring = ring;
        this.key = key;
        n = ring.length();
        m = key.length();
        memo = new int[n][m];
        for (int i = 0; i < n; i++) {
            char c = ring.charAt(i);
            if (dic.containsKey(c)) {
                dic.get(c).add(i);
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                dic.put(c, list);
            }
        }
        return backTrack(0, 0);
    }

    /**
     * @param i 当前轮盘所指向的位置
     * @param j 当前key输入的位置
     * @return
     */
    private int backTrack(int i, int j) {
        if (j == m) return 0;
        if (memo[i][j] != 0) return memo[i][j];

        int res = Integer.MAX_VALUE;
        for (int idx : dic.get(key.charAt(j))) {
            int instance = Math.abs(idx - i);
            instance = Math.min(instance, n - instance);//将轮盘转到idx的最短距离
            int after = backTrack(idx, j + 1);
            res = Math.min(res, instance + after + 1);
        }
        memo[i][j] = res;
        return res;
    }

    public int trap(int[] height) {
        int rain = 0;
        int n = height.length;
        int[] left = new int[n];
        int[] right = new int[n];
        left[0] = height[0];
        right[n - 1] = height[n - 1];

        for (int i = 1; i < n; i++) {
            left[i] = Math.max(left[i - 1], height[i]);
        }
        for (int i = n - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], height[i]);
        }

        for (int i = 0; i < n; i++) {
            rain += Math.min(left[i], right[i]) - height[i];
        }

        return rain;
    }

    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - i][j];
                matrix[n - 1 - i][j] = temp;
            }
        }

        for (int i = 1; i <= n - 1; i++) {
            for (int j = 0; j <= i - 1; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }

    public boolean canJump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        if (dp[0] >= n - 1) return true;
        for (int i = 1; i < n; i++) {
            if (dp[i - 1] < i) {
                continue;
            }
            dp[i] = Math.max(dp[i - 1], i + nums[i]);
            if (dp[i] >= n - 1) {
                return true;
            }
        }
        return false;
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        Arrays.sort(intervals, (o1, o2) -> {
            return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0];
        });

        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int L = intervals[i][0], R = intervals[i][1];
            if (list.size() == 0 || list.get(list.size() - 1)[1] < L) {
                list.add(new int[]{L, R});
            } else {
                list.get(list.size() - 1)[1] = Math.max(list.get(list.size() - 1)[1], R);
            }
        }
        return list.toArray(new int[list.size()][]);
    }

    char[][] board;
    String word;

    public boolean exist(char[][] board, String word) {
        this.board = board;
        this.word = word;
        int row = board.length, col = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (findWord(i, j, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    boolean findWord(int i, int j, int idx) {
        int row = board.length, col = board[0].length;
        int n = word.length();
        if (idx == n - 1 && board[i][j] == word.charAt(idx)) {
            return true;
        }
        if (i < 0 || j < 0 || i >= row || j >= col || board[i][j] != word.charAt(idx)) {
            return false;
        }

        char temp = board[i][j];
        board[i][j] = '0';
        if (i + 1 < row) {
            if (findWord(i + 1, j, idx + 1)) return true;
        }
        if (i - 1 >= 0) {
            if (findWord(i - 1, j, idx + 1)) return true;
        }
        if (j + 1 < col) {
            if (findWord(i, j + 1, idx + 1)) return true;
        }
        if (j - 1 >= 0) {
            if (findWord(i, j - 1, idx + 1)) return true;
        }
        board[i][j] = temp;
        return false;
    }
}
